package com.jia.leetCode;

public class Pro1337  {
    class Pair implements Comparable<Pair>{
        int index;
        int count;
        public Pair(int index, int count) {
            this.index = index;
            this.count = count;
        }
        @Override
        public int compareTo(Pair o) {
            return this.count - o.count;
        }
    }
    public int[] kWeakestRows(int[][] mat, int k) {
        Pair[] ps = new Pair[mat.length];
        for(int r = 0; r < mat.length; r++) {
            int count = 0;
            for(int c = 0; c < mat[0].length; c++) {
                if(mat[r][c] == 1) {
                    ++count;
                }
            }
            ps[r] = new Pair(r, count);
        }
        bubbleSort(ps);//排序
        int[] ans = new int[k];
        for(int i = 0; i < k; i++) {
            ans[i] = ps[i].index;
        }
        return ans;
    }
    public void bubbleSort(Pair[] ps) {
        boolean isSort = true;
        for(int i = ps.length - 1; i >0 ; i--) {
            isSort = true;
            for(int j = 0; j < i; j++) {
                if(ps[j].compareTo(ps[j+1]) > 0) {
                    isSort = false;
                    //swap
                    Pair tmp = ps[j];
                    ps[j] = ps[j+1];
                    ps[j+1] = tmp;
                }
            }
            if(isSort) { break; }
        }
    }
}
